package LeetCode1;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 最后一块石头的重量
 * 要先拿出两个最大的，所以用最大堆
 *
 * @author 是阿秋啊
 * @date 2022/03/17 13:33
 **/
public class Num1046 {
    public int lastStoneWeight(int[] stones) {
        if (stones.length == 1) {
            return stones[0];
        }
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //将数组入堆
        for (int i : stones) {
            queue.offer(i);
        }
        //此时队列排序完成,遍历队列
        //当队列长度小于等于1时终止操作
        while (queue.size() > 1) {
            //将前两个最重的石头取出
            int m = queue.poll();
            int n = queue.poll();
            if (m > n) {
                queue.offer(m - n);
            }
        }
        return queue.isEmpty() ? 0 : queue.poll();
    }
}
